/**
 * @file 010.和为k的子数组.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-08
 *
 * @copyright Copyright (c) 2021
 *
 * 前缀和 **
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        // 滑窗失效，有负数例
        // 法一：枚举 固定边界 O(N^2)
#if 0
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            // 固定右边界，枚举左边界[j,i]
            // for (int j = i; j >= 0; --j) {
            // 固定左边界，枚举右边界[i,j]
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum == k) {
                    ++cnt;
                }
            }
        }
        return cnt;
#endif
#if 0
        // 法二：前缀和 O(N^2)
        int n = nums.size();
        vector<int> preSum(n + 1, 0);
        // 构建前缀和
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int cnt = 0;
        // 枚举前缀和 区间和=前缀和端点之差
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (preSum[j] - preSum[i] == k) {
                    ++cnt;
                }
            }
        }
        return cnt;
#endif
#if 1
        // 法三：前缀和+哈希
        // 由于只关心次数，不关心具体解，使用哈希加速运算
        int n = nums.size();
        unordered_map<int, int> mp; // {和：次数}
        mp[0] = 1;
        int cnt = 0;
        int preSum = 0;
        for (int i = 0; i < n; ++i) {
            preSum += nums[i];
            if (mp.find(preSum - k) != mp.end()) {
                cnt += mp[preSum - k];
            }
            ++mp[preSum];
        }
        return cnt;
#endif
    }
};

int main()
{
    vector<int> nums1 = {1, 1, 0, 1, 2};
    vector<int> nums2 = {-1, -1, 1};
    cout << Solution().subarraySum(nums1, 2) << endl; // 4
    cout << Solution().subarraySum(nums2, 0) << endl; // 1
    return 0;
}